package com.ljy.my_study.lintcode.二叉树的路径和;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import com.ljy.my_study.util.TreeNodeUtil;
import com.ljy.my_study.util.TreeNodeUtil.TreeNode;

/** 
* @author James
* @date 2018年9月29日 
*/
public class TestMain {
//	描述
//	给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。
//
//	一个有效的路径，指的是从根节点到叶节点的路径。
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给定一个二叉树，和 目标值 = 5:
//
//	     1
//	    / \
//	   2   4
//	  / \
//	 2   3
//	返回：
//
//	[
//	  [1, 2, 2],
//	  [1, 4]
//	]
	public static void main(String[] args) {
//		TreeNode head=TreeNodeUtil.deserialize("1,2,3,4,#,#,#,8,9");
//		System.out.println(head);
//		System.out.println(findAllTreePaths(head,4));
//		int[] nums= {1,2,3,4,5};
		int[] nums= {1};
		System.out.println(list(nums,1));
	}
	
	public static List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
		
		return null;
	}
	//找出集合全部元素相加等于target的所有可能
	public static List<List<Integer>> list(int[] nums,int target) {
		List<List<Integer>> listList=new ArrayList<>();
		if(nums.length==1&&nums[0]==target) {
			List<Integer> list=new ArrayList<>();
			list.add(0);
			listList.add(list);
			return listList;
		}
		Queue<Group> q=new LinkedList<>();
		int count=1;
		while(count<nums.length) {
			q.offer(new Group(nums[count-1],count-1));
			while(!q.isEmpty()) {
				list(listList,q,nums,target,count);
				count++;
			}
		}
		return listList;
	}
	
	public static void list(List<List<Integer>> listList,Queue<Group> q,int[] nums,int target,int count){
		Group g=q.poll();
		if(g.sum==target) {
			listList.add(g.indexList);
			return;
		}else if(g.val>target) {
			return;
		}
		for(int i=count;i<nums.length;i++) {
			if(g.sum+nums[i]<=target) {
				Group newG=new Group(nums[i],g.sum,i,g.indexList);
				q.offer(newG);
				list(listList,q,nums,target,i+1);
			}
		}
	}
	
	public static Map<List<Integer>,Integer> findAllTreePaths(TreeNode root,int target) {
		if(root==null) {
		}
		List<List<Integer>> listList=new ArrayList<>();
		findTreePath(listList,new ArrayList<>(),root,target);
		Map<List<Integer>,Integer> map=new HashMap<>();
		for(List<Integer> l:listList) {
			map.put(l, l.size());
		}
		return map;
	}
	
	public static void findTreePath(List<List<Integer>> listList,List<Integer> list,TreeNode node,int target) {
		if(node==null) {
			return;
		}
		List<Integer> newList=new ArrayList<>(list);
		newList.add(node.val);
		if(node.left==null&&node.right==null) {
			listList.add(newList);
		}else {
			if(list.size()>=target)return;
			if(node.left!=null) findTreePath(listList,newList,node.left,target);
			if(node.right!=null) findTreePath(listList,newList,node.right,target);
		}
	}
	
	public static class Group {
		public int index;
		public int val;
		public int sum;
		public List<Integer> indexList;
		
		public Group(int val,int index) {
			this.val=val;
			this.sum=val;
			this.index=index;
			this.indexList=new ArrayList<>();
			this.indexList.add(index);
		}
		
		public Group(int val,int lastSum,int index,List<Integer> lastIndexList){
			this.indexList=new ArrayList<>(lastIndexList);
			this.indexList.add(index);
			this.sum=lastSum+val;
			this.val=val;
			this.index=index;
		}

		@Override
		public String toString() {
			return "{\"index\":\"" + index + "\",\"val\":\"" + val + "\",\"sum\":\"" + sum + "\",\"indexList\":\""
					+ indexList + "\"} ";
		}
	}
}
